{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Shortest Distance to Target Color"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #binary-search #dynamic-programming"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #二分查找 #动态规划"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: shortestDistanceColor"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #与目标颜色间的最短距离"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个数组&nbsp;<code>colors</code>，里面有&nbsp;&nbsp;<code>1</code>、<code>2</code>、&nbsp;<code>3</code> 三种颜色。</p>\n",
    "\n",
    "<p>我们需要在&nbsp;<code>colors</code> 上进行一些查询操作 <code>queries</code>，其中每个待查项都由两个整数 <code>i</code> 和 <code>c</code> 组成。</p>\n",
    "\n",
    "<p>现在请你帮忙设计一个算法，查找从索引&nbsp;<code>i</code>&nbsp;到具有目标颜色&nbsp;<code>c</code>&nbsp;的元素之间的最短距离。</p>\n",
    "\n",
    "<p>如果不存在解决方案，请返回&nbsp;<code>-1</code>。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>colors = [1,1,2,1,3,2,2,3,3], queries = [[1,3],[2,2],[6,1]]\n",
    "<strong>输出：</strong>[3,0,3]\n",
    "<strong>解释： </strong>\n",
    "距离索引 1 最近的颜色 3 位于索引 4（距离为 3）。\n",
    "距离索引 2 最近的颜色 2 就是它自己（距离为 0）。\n",
    "距离索引 6 最近的颜色 1 位于索引 3（距离为 3）。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>colors = [1,2], queries = [[0,3]]\n",
    "<strong>输出：</strong>[-1]\n",
    "<strong>解释：</strong>colors 中没有颜色 3。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= colors.length &lt;= 5*10^4</code></li>\n",
    "\t<li><code>1 &lt;= colors[i] &lt;= 3</code></li>\n",
    "\t<li><code>1&nbsp;&lt;= queries.length &lt;= 5*10^4</code></li>\n",
    "\t<li><code>queries[i].length == 2</code></li>\n",
    "\t<li><code>0 &lt;= queries[i][0] &lt;&nbsp;colors.length</code></li>\n",
    "\t<li><code>1 &lt;= queries[i][1] &lt;= 3</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [shortest-distance-to-target-color](https://leetcode.cn/problems/shortest-distance-to-target-color/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [shortest-distance-to-target-color](https://leetcode.cn/problems/shortest-distance-to-target-color/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,1,2,1,3,2,2,3,3]\\n[[1,3],[2,2],[6,1]]', '[1,2]\\n[[0,3]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestDistanceColor(self, colors: List[int], queries: List[List[int]]) -> List[int]:\n",
    "      n = len(colors)\n",
    "      dist = [[-1]*n for _ in range(3)]\n",
    "      queue = [[] for _ in range(3)]\n",
    "      for i in range(n):\n",
    "        dist[colors[i]-1][i] = 0\n",
    "        queue[colors[i]-1].append(i)\n",
    "      \n",
    "      for i in range(3):\n",
    "        while queue[i]:\n",
    "          temp = []\n",
    "          for j in queue[i]:\n",
    "            if j > 0 and dist[i][j-1] == -1:\n",
    "              dist[i][j-1] = dist[i][j] + 1\n",
    "              temp.append(j-1)\n",
    "            if j < n-1 and dist[i][j+1] == -1:\n",
    "              dist[i][j+1] = dist[i][j] + 1\n",
    "              temp.append(j+1)\n",
    "          queue[i] = temp\n",
    "      \n",
    "      for i in range(len(queries)):\n",
    "        queries[i] = dist[queries[i][1]-1][queries[i][0]]\n",
    "      return queries"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestDistanceColor(self, colors: List[int], queries: List[List[int]]) -> List[int]:\n",
    "      n = len(colors)\n",
    "      dist = [[-1]*n for _ in range(3)]\n",
    "      queue = [[] for _ in range(3)]\n",
    "      for i in range(n):\n",
    "        dist[colors[i]-1][i] = 0\n",
    "        queue[colors[i]-1].append(i)\n",
    "      \n",
    "      for i in range(3):\n",
    "        while queue[i]:\n",
    "          temp = []\n",
    "          for j in queue[i]:\n",
    "            if j > 0 and dist[i][j-1] == -1:\n",
    "              dist[i][j-1] = dist[i][j] + 1\n",
    "              temp.append(j-1)\n",
    "            if j < n-1 and dist[i][j+1] == -1:\n",
    "              dist[i][j+1] = dist[i][j] + 1\n",
    "              temp.append(j+1)\n",
    "          queue[i] = temp\n",
    "      \n",
    "      for i in range(len(queries)):\n",
    "        queries[i] = dist[queries[i][1]-1][queries[i][0]]\n",
    "      return queries"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestDistanceColor(self, colors: List[int], queries: List[List[int]]) -> List[int]:\n",
    "      n = len(colors)\n",
    "      dist = [[-1]*n for _ in range(3)]\n",
    "      queue = [[] for _ in range(3)]\n",
    "      for i in range(n):\n",
    "        dist[colors[i]-1][i] = 0\n",
    "        queue[colors[i]-1].append(i)\n",
    "      \n",
    "      for i in range(3):\n",
    "        while queue[i]:\n",
    "          temp = []\n",
    "          for j in queue[i]:\n",
    "            if j > 0 and dist[i][j-1] == -1:\n",
    "              dist[i][j-1] = dist[i][j] + 1\n",
    "              temp.append(j-1)\n",
    "            if j < n-1 and dist[i][j+1] == -1:\n",
    "              dist[i][j+1] = dist[i][j] + 1\n",
    "              temp.append(j+1)\n",
    "          queue[i] = temp\n",
    "      \n",
    "      for i in range(len(queries)):\n",
    "        queries[i] = dist[queries[i][1]-1][queries[i][0]]\n",
    "      return queries"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestDistanceColor(self, colors: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        n = len(colors)\n",
    "        each_color = [[] for _ in range(4)]\n",
    "        for i in range(n):\n",
    "            each_color[colors[i]].append(i)\n",
    "        ans = []\n",
    "        for i, (target, c) in enumerate(queries):\n",
    "            if len(each_color[c])==0:\n",
    "                ans.append(-1)\n",
    "                continue\n",
    "            insert = bisect.bisect_left(each_color[c], target)\n",
    "            left_nearest = abs(each_color[c][max(insert-1, 0)]- target) \n",
    "            right_nearest = abs(each_color[c][min(insert, len(each_color[c])-1)] - target)\n",
    "            ans.append((min(left_nearest, right_nearest)))\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestDistanceColor(self, colors: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        dic = defaultdict(list)\n",
    "        for i, c in enumerate(colors):\n",
    "            dic[c].append(i)\n",
    "        ans = []\n",
    "        for i, c in queries:\n",
    "            if not dic[c]:\n",
    "                ans.append(-1)\n",
    "            else:\n",
    "                arr = dic[c]\n",
    "                j = bisect_left(arr, i)\n",
    "                if j == len(arr):\n",
    "                    ans.append(i - arr[-1])\n",
    "                else:\n",
    "                    d = arr[j] - i\n",
    "                    if j:\n",
    "                        d = min(d, i - arr[j-1])\n",
    "                    ans.append(d)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # % dp + 预处理\n",
    "    # https://leetcode.cn/problems/shortest-distance-to-target-color/solution/yu-mu-biao-yan-se-jian-de-zui-duan-ju-chi-by-leetc/\n",
    "    def shortestDistanceColor1(self, colors: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        def check(c):\n",
    "            distance = [n + 1] * n\n",
    "            i = -n - 1\n",
    "            for j in range(n):\n",
    "                if colors[j] == c:\n",
    "                    i = j\n",
    "                distance[j] = distance[j] if distance[j] < j - i else j - i\n",
    "\n",
    "            i = 2 * n + 1\n",
    "            for j in range(n - 1, -1, -1):\n",
    "                if colors[j] == c:\n",
    "                    i = j\n",
    "                distance[j] = distance[j] if distance[j] < i - j else i - j\n",
    "            return distance\n",
    "\n",
    "        n = len(colors)\n",
    "        res = [check(c) for c in range(1, 4)]\n",
    "        return [res[c - 1][i] if res[c - 1][i] < n + 1 else -1 for i, c in queries]\n",
    "   \n",
    "\n",
    "\n",
    "    # 二分查找\n",
    "    # O(Q∗logC) O(C)\n",
    "    def shortestDistanceColor(self, colors: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        color_idxs = defaultdict(list)\n",
    "        for i, c in enumerate(colors):\n",
    "            color_idxs[c].append(i)\n",
    "        res = []\n",
    "        for i, c in queries:\n",
    "            if c not in color_idxs: #这个颜色不存在\n",
    "                res.append(-1)\n",
    "            elif colors[i] == c:  #就是自己\n",
    "                res.append(0)\n",
    "            else:\n",
    "                a = color_idxs[c]\n",
    "                r = bisect.bisect_left(a, i)\n",
    "                if r == 0:\n",
    "                    res.append(a[0] - i)\n",
    "                elif r == len(a):\n",
    "                    res.append(i - a[-1])\n",
    "                else:\n",
    "                    l = r - 1\n",
    "                    res.append(min(a[r] - i, i - a[l]))\n",
    "\n",
    "        return res\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestDistanceColor(self, colors: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        inf = float('inf')\n",
    "        n=len(colors)\n",
    "        dis = [[inf,inf,inf] for _ in range(n)]\n",
    "        tmp_index = [-1,-1,-1]\n",
    "        for i in range(n):\n",
    "            tmp_index[colors[i]-1]=i\n",
    "            for j in range(3):\n",
    "                if tmp_index[j]!=-1:\n",
    "                    dis[i][j] = i-tmp_index[j]\n",
    "        \n",
    "        # print(dis)\n",
    "        tmp_index = [-1,-1,-1]\n",
    "        for i in range(n-1, -1, -1):\n",
    "            tmp_index[colors[i]-1]=i\n",
    "            for j in range(3):\n",
    "                if tmp_index[j]!=-1:\n",
    "                    dis[i][j] = min(dis[i][j], tmp_index[j]-i)\n",
    "        \n",
    "        # print(dis)\n",
    "        ans = []\n",
    "        for q in queries:\n",
    "            ans.append(-1 if dis[q[0]][q[1]-1]==inf else dis[q[0]][q[1]-1])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestDistanceColor(self, colors: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        dic = defaultdict(list)\n",
    "        for i, c in enumerate(colors):\n",
    "            dic[c].append(i)\n",
    "        ans = []\n",
    "        print(dic)\n",
    "        for i, c in queries:\n",
    "            if not dic[c]:\n",
    "                ans.append(-1)\n",
    "            else:\n",
    "                arr = dic[c]\n",
    "                j = bisect_left(arr, i)\n",
    "                if j == len(arr):\n",
    "                    ans.append(i - arr[-1])\n",
    "                else:\n",
    "                    d = arr[j] - i\n",
    "                    if j:\n",
    "                        d = min(d, i - arr[j-1])\n",
    "                    ans.append(d)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestDistanceColor(self, colors: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        @cache\n",
    "        def findc(mid,target):\n",
    "            \n",
    "            if colors[mid]==target:\n",
    "                return 0\n",
    "            d=1\n",
    "            while mid-d>=0 or mid+d<n:\n",
    "                if (mid-d>=0 and colors[mid-d]==target) or (mid+d<n and colors[mid+d]==target):\n",
    "                    return d\n",
    "                d+=1\n",
    "            return -1\n",
    "        n=len(colors)\n",
    "        ans=[]\n",
    "        for i,c in queries:\n",
    "            ans.append(findc(i,c))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "    给一个index，告诉我离这个index，最近的某color最近的距离\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def shortestDistanceColor(self, colors: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        n = len(colors)\n",
    "        res = []\n",
    "        l = {}\n",
    "        r = {}\n",
    "        r[1] = [0] * n\n",
    "        r[2] = [0] * n\n",
    "        r[3] = [0] * n\n",
    "        s1 = s2 = s3 = -1\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            v = colors[i]\n",
    "            if v == 1:\n",
    "                s1 = i\n",
    "            elif v == 2:\n",
    "                s2 = i\n",
    "            else:\n",
    "                s3 = i\n",
    "            r[1][i], r[2][i], r[3][i] = s1, s2, s3\n",
    "        l[1] = [0] * n\n",
    "        l[2] = [0] * n\n",
    "        l[3] = [0] * n\n",
    "        s1 = s2 = s3 = -1\n",
    "        for i, v in enumerate(colors):\n",
    "            if v == 1:\n",
    "                s1 = i\n",
    "            elif v == 2:\n",
    "                s2 = i\n",
    "            else:\n",
    "                s3 = i\n",
    "            l[1][i], l[2][i], l[3][i] = s1, s2, s3\n",
    "        \n",
    "        for (idx, c) in queries:\n",
    "            if l[c][idx] == -1 and r[c][idx] == -1:\n",
    "                res.append(-1)\n",
    "            else:\n",
    "                if l[c][idx] == -1:\n",
    "                    res.append(r[c][idx] - idx)\n",
    "                elif r[c][idx] == -1:\n",
    "                    res.append(idx - l[c][idx])\n",
    "                else:\n",
    "                    res.append(min(r[c][idx] - idx, idx - l[c][idx]))\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestDistanceColor(self, colors: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        n = len(colors)\n",
    "        # dp[i][j] 第i个索引到第j个颜色最短距离\n",
    "        dp = [[float(\"inf\") for _ in range(3)] for _ in range(n)]\n",
    "        dp[0][colors[0] - 1] = 0\n",
    "        dp[-1][colors[-1] - 1] = 0\n",
    "        for i in range(1, n):\n",
    "            for j in range(3):\n",
    "                if j == colors[i] - 1:\n",
    "                    dp[i][j] = 0\n",
    "                else:\n",
    "                    dp[i][j] = min(dp[i][j], dp[i - 1][j] + 1)\n",
    "        \n",
    "        for i in range(n - 2, -1, -1):\n",
    "            for j in range(3):\n",
    "                if j == colors[i] - 1:\n",
    "                    dp[i][j] = 0\n",
    "                else:\n",
    "                    dp[i][j] = min(dp[i][j], dp[i + 1][j] + 1)\n",
    "\n",
    "        res = []\n",
    "        for item in queries:\n",
    "            dist = dp[item[0]][item[1] - 1]\n",
    "            if dist == float(\"inf\"):\n",
    "                dist = -1\n",
    "            res.append(dist)\n",
    "        return res"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
